void
swap(int *arr, int i, int j)
{
	int temp = arr[i];
	arr[i] = arr[j];
	arr[j] = temp;
}

/*
 * 'pivot' is chosen to be the first element: arr[p]
 */
int 
partition(int *arr, int p, int q)
{
	int pivot, i, j;
	pivot = arr[p];
	i = p;
	j = p+1;
	for( ; j<=q; j++) 
		if(arr[j] <= pivot)
			swap(arr, ++i, j);
	swap(arr, p, i);
	return i;
}

void
quicksort(int *arr, int p, int q)
{
	int r;
	if(p<q) {
		r = partition(arr, p, q);
		quicksort(arr, p, r-1);
		quicksort(arr, r+1, q);
	}
}
